1. Field of the Invention
The present invention pertains to information theory, and particularly to a class of binary parallel concatenated recursive systematic convolutional codes known as turbo codes, as well as apparatus and method using turbo codes.
2. Related Art and Other Considerations
Data transmitted over a channel data may be corrupted from its original form. One example is data transmitted over a wireless, e.g., radio frequency, interface between a transmitter and receiver (one of which may be a mobile or cellular telephone, for example). Various encoding techniques have been employed so that errors in a string of received data bits may be located and, if possible, corrected. Such error correction techniques typically employ utilization of error correction code(s) which operate upon the original data in order to generate additional information which is transmitted along with the original data. Inclusion of the additional information with the received data facilitates the location and possible correction of error bits by the receiver, so that the receiver may ultimately obtain the original data as transmitted by the transmitter.
Many types of codes have been utilized in the error correction branch of information theory. Turbo codes, introduced in 1993, are considered to have high error correction capability and good performance. See, e.g., C. Berrout, A. Glavieux, and P. Thitimajshima, “Near Shannon Limit Error Correcting Coding and Decoding: Turbo Codes”, Proc. ICC93, pp. 1064–1070, May 1993, and C. Berrout and A. Glavieux, “Near Optimum Error Correcting Coding and Decoding: Turbo Codes”, IEEE Trans. On Communications, Vol. 44, No. 10, pp. 1261–1271, October. 1996.
The basic structure of turbo codes is the parallel concatenation of two or more component codes applied to different interleaved versions of the same information sequence. Recursive systematic convolutional (RSC) codes are used in general as the component codes. The constraint length K for the RSC codes could be shorter than that of conventional convolutional codes to achieve the equivalent or better performance.
FIG. 10 illustrates the structure of an example turbo code encoder. The example encoder 1000 of FIG. 10 comprises two RSC encoders 10021 and 10022 concatenated in parallel. In view of there being two encoders (e.g., M=2), the code rate of the illustrative turbo code encoder has a code rate R=⅓, since (as an approximation) R=1/(M+1)). The input to the first RSC encoder 10021 is the original information sequence d. The original information sequence is also applied to an interleaver 1004 to produce an interleaved version d′ of the original information sequence d. The interleaved version d′ of the information sequence is the input to the second RSC encoder 10022. Since the RSC is the systematic encoder, the outputs from the turbo encoder are sequences of systematic u (=d) and redundant parts x(1) (output from the first RSC encoder 10021) and x(2) (output from the second encoder 10022). In other words, the output of the encoder 1000 is in the form u1, x1(1), x1(2), u2, x2(1), x2(2), where uk is the kth systematic bit (i.e., data bit), xk(1) is the parity output from the first RSC encoder 10021 associated with the kth systematic bit uk; and xk(2) is the parity output from the second RSC encoder 10022 associated with the kth systematic bit uk.
The decoding procedure for the turbo codes is known as iterative decoding. An example conventional turbo decoder, shown as decoder 1100 in FIG. 11, is comprised of two component decoders 11021, and 11022 (corresponding to the RSC encoders 10021 and 10022, respectively); an interleaver 1104 (which is the same type interleaver as interleaver 1004 used in the corresponding turbo encoder); and, a de-interleaver 1106 (which also corresponds to the interleaver 1004). The two component decoders 11021 and 11022 are soft-input and soft-output (SISO) decoders. The outputs of the two component decoders 11021 and 11022 are likelihood information concerning the coded data sequence.
The inputs to the turbo decoder 1100 are the channel measurements made at the detector for the systematic part y(0), the redundant parts y(1) and Y(2). These inputs correspond to u, x(1), and x(2), respectively. The component decoder computes, for the kth decoded bit dk, the probability that this bit was 1 or 0, after the received symbol sequence y={y(0), y(1), y(2)} is given.
Computing this probability is equivalent to finding the a posteriori log likelihood ratio (LLR) L({circumflex over (d)})=L(dk| y), as shown by Expression (1).
                              L          ⁡                      (                                          d                k                            ❘                              y                _                                      )                          =                  ln          ⁡                      (                                          P                ⁡                                  (                                                            d                      k                                        =                                          1                      ❘                                              y                        _                                                                              )                                                            P                ⁡                                  (                                                            d                      k                                        =                                          0                      ❘                                              y                        _                                                                              )                                                      )                                              Expression        ⁢                                  ⁢                  (          1          )                    In Expression 1, P(dk=1) is the probability that the bit dk=1, and P(dk=0) is the probability that the bit dk=0. The input LLR for the data bit d to the component decoder, designated Lin ({circumflex over (d)}), is expressed by Expression (2).Lin({circumflex over (d)})=y(0)+L(d)  Expression (2)
In Expression 2, L(d) is the a priori LLR of the d. For a systematic code, it has been shown (by C. Berrout, A. Glavieux, and P. Thitimajshima, “Near Shannon Limit Error Correcting Coding and Decoding: Turbo Codes”, Proc. ICC93, pp. 1064–1070, May 1993) that the LLR equals to
                                                                        L                ⁡                                  (                                      d                    ^                                    )                                            =                                                                    L                    in                                    ⁡                                      (                                          d                      ^                                        )                                                  +                                  Le                  ⁡                                      (                                          d                      ^                                        )                                                                                                                          =                                                y                                      (                    0                    )                                                  +                                  L                  ⁡                                      (                    d                    )                                                  +                                  Le                  ⁡                                      (                                          d                      ^                                        )                                                                                                          Expression        ⁢                                  ⁢                  (          3          )                    
In Expression (3) Le({circumflex over (d)}), called the extrinsic LLR, represents extra knowledge that is gleaned from the decoding process. In the iterative decoding procedure, the extrinsic LLR calculated from the previous component decoder will be set as a priori LLR for the next component decoder. At the very first component decoding, L(d) is set as 0. Since the component decoders 1102 are connected each other together with the interleaver 1104/de-interleaver 1106 as seen in FIG. 11, these operations are repeated. With more decoding iterations, the accuracy of the likelihood of the systematic bits L({circumflex over (d)}) becomes better. After a number of iterations, finally the sign of L({circumflex over (d)}) will be the decoder decision for the result, and the amplitude of L({circumflex over (d)}) denotes the reliability of that decision. Thus, using turbo decoding, the error correcting performance is improved through the iterative procedure.
Further discussions of principles involved in turbo coding and decoding are provided in B. Sklar, “A Primer on Turbo Code Concepts,” IEEE Communications Magazine, pp. 94–102, December 1997; A. Ushirokawa, T. Okamura, N. Kamiya, and B. Vucetic, “Principles of Turbo Codes and Their Applications to Mobile communications,” IEICE Trans. On Fundamentals, vol. E81-A, No. 7, July 1998; J. P. Woodard and L. Hanzo, “Comparative Study of Turbo Decoding Techniques: An Overview,” IEEE Trans. On Vehicular Technology, vol. 49, no. 6, pp. 2208–2233, November 2000.
Characteristics and performance of turbo codes are shown in P. Jung, “Comparison of Turbo-Code Decoders Applied to Short Frame Transmission Systems,” IEEE Journal on Selected Areas on Communications, vol. 14, no. 3, pp. 530–537, April 1996; P. Jung and M. Baβhen, “Results on Turbo-Codes for Speech Transmission in a Joint Detection CDMA Mobile Radio System with Coherent Receiver Antenna Diversity,” IEE Trans. on Vehicular Technology, vol. 46, no. 4, November 1997; H. Koorapaty, Y. E. Wang, and K. Balachandran, “Performance of Turbo Codes with Short Frame Sizes”, Proc. of 1997; and P. Frenger, “Turbo Decoding for Wireless Systems with Imperfect Channel Estimates,” IEEE Trans. on Communications, vol. 48, no. 9, September 2000. A turbo code decoding analysis is provided in D. Divsalar, S. Dolinar and F. Pollara, “Iteractive Turbo Decoder Analysis Based on Density Evolution,” IEEE Journal on Selected Areas in Communication, vol. 19, no. 5, May 2001. All the foregoing are incorporated by reference in their entirety.
In any type of decoder (not just turbo decoders), the accuracy of the decoder is heavily dependent upon the reliability of the input for the decoder. What is sought, therefore, and an object of the present invention, is a technique for improving the accuracy of a turbo decoder by improving reliability of its inputs.